import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 22652
 * Date: 2024-06-16
 * Time: 16:16
 */
public class test_4 {
    class Solution {
        public int minimumTotal(List<List<Integer>> triangle) {
            int n = triangle.size();
            int[][] dp = new int[n+1][n+1];
            //倒数第二行，倒数第二列
            for(int i = n - 1; i >= 0; i--) {
                for(int j = triangle.get(i).size() - 1; j >= 0; j--) {
                    dp[i][j] = Math.min(dp[i+1][j], dp[i+1][j+1]) + triangle.get(i).get(j);
                }
            }
            return dp[0][0];
        }
    }

}
